import java.util.ArrayList;
import java.util.List;

public class Test2 {
    String[] letter_map = {" ","*","abc","def","ghi","jkl"
            ,"mno","pqrs","tuv","wxyz"};
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits){
        if(digits == null || digits.length() == 0){
            return res;
        }
        backtrack(digits,new StringBuilder(),0);
        return res;
    }
    //回溯方法的三个参数：输入的数字、根据数字拼接的字符、数字的开始下标
    //(index = 0 意为从输入的字符串0下标的数字开始遍历)
    void backtrack(String digits, StringBuilder letter, int index) {
        //base case（当遍历到最后一个数字后结束）
        if(index == digits.length()){
            //将子结果转化成String类添加到最终结果中
            res.add(letter.toString());
            return;
        }
        //从输入的字符串中根据index下标获取数字
        char c = digits.charAt(index);
        int pos = c - '0';
        //获取数字代表的字符串
        String map_string = letter_map[pos];
        for (int i = 0; i < map_string.length(); i++) {
            //做选择：将字符拼接到子结果中
            letter.append(map_string.charAt(i));
            //进入下一层决策
            //固定元素之间的相对位置防止出现重复
            backtrack(digits,letter,index+1);
            //撤销选择：删除子结果letter最后一位
            letter.deleteCharAt(letter.length()-1);
        }
    }
}
